/*
题目: 优势洗牌
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

https://leetcode.cn/problems/advantage-shuffle
 */
public class AdvantageCount {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;

        Integer[] idx1 = new Integer[n];
        Integer[] idx2 = new Integer[n];
        for (int i = 0; i < n; i ++)
            idx1[i] = idx2[i] = i;

        Arrays.sort(idx1, (o1, o2) -> {return nums1[o1] - nums1[o2];});
        Arrays.sort(idx2, (o1, o2) -> {return nums2[o1] - nums2[o2];});

        int right = n - 1, left = 0;
        int[] src = new int[n];
        // 目的是寻找符合 nums2 的元素, 需要去 遍历 idx1
        // left 和 right 同时是 src 和 nums2 的下标, 因为目的就是围着 nums2 找 src
        for (int i = 0; i < n; i ++) {
            if (nums1[idx1[i]] > nums2[idx2[left]]) {
                src[idx2[left ++]] = nums1[idx1[i]];
            } else {
                src[idx2[right --]] = nums1[idx1[i]];
            }
        }

        return src;
    }
}
